/*
直接插入排序，实现数组的递增有序
*/

#include<iostream>
#include<vector>
using namespace std;

// 将R[i]有序插入到R[0..i-1]中，假定R[0..i-1]有序
void Insert(vector<int>&R, int i)
{
	// 记录需要插入的值
	int tmp = R[i];
	int j = i-1;
	
	// 找R[i]的插入位置
	do
	{
		// 将关键字大于R[i]的元素后移
		R[j+1] = R[j];
		j--;
	} while(j>=0 && R[j]>tmp); // 直到R[j]<=tmp为止
	
	// 在j+1处插入R[i]
	R[j+1]=tmp;
}


/* 迭代算法 */
void InsertSort1(vector<int> &R) 		//迭代算法：直接插入排序
{
	// 获取长度
	int n = R.size();
	
	for (int i=1;i<n;i++)
	{
		// 反序时
		if (R[i] < R[i-1])
			Insert(R,i);
	}
}

/* 先递后合算法 */
void InsertSort21(vector<int> &R, int i) // 递归直接插入排序
{
	if(i==0) return;
	InsertSort21(R, i-1);
	
	// 反序时
	if (R[i] < R[i-1])
		Insert(R, i);
}

// 递归算法：直接插入排序
void InsertSort2(vector<int> &R)
{
	// 向量长度
	int n = R.size();
	
	// 直接插入排序
	InsertSort21(R, n-1);
}

/* 先合后递算法 */
void InsertSort31(vector<int> &R,int i) //递归直接插入排序
{
	// 求向量长度
	int n = R.size();
	if(i<1 || i>n-1) return;
	
	// 反序时
	if (R[i] < R[i-1])
		Insert(R, i);
	
	
	InsertSort31(R, i+1);
}

// 递归算法：直接插入排序
void InsertSort3(vector<int> &R)
{
	InsertSort31(R, 1);
}

// 打印向量信息
void disp(vector<int>&a)
{
	for(int i=0; i<a.size(); i++)
		printf("%d ",a[i]);
	printf("\n");
}


int main()
{
	// 创建向量
	vector<int> a={2, 5, 4, 1, 3};
	
	// 打印向量
	printf("a: "); 
	disp(a);
	
	// 插入排序
	InsertSort2(a);
	
	// 打印向量
	printf("排序\na: "); 
	disp(a);
	return 0;
}
